1. Field of the Invention
The present invention is directed to a method for generating and calculating reliability information with the use of a symbol detector used in a receiver for a digital communication system.
2. Description of the Related Art
Digital telecommunication systems convey digital information (i.e., bits or groups of bits) over various types of communication channels such as air, coaxial cables, telephone lines, fiber optic lines or any other well known medium through which communication signals propagate. The digital information is transmitted and received with the use of well known standard transmitter and receiver equipment. FIG. 1 depicts a model of a typical digital communication system comprising a transmitter connected to a receiver via a communication channel. The transmitter comprises convolutional encoder 102 coupled to Interleaver 104 which is coupled to modulator 106. The input signal bi is typically a string or a group of bits (e.g., 0,1) arranged in any well known format. The digital bits represent any type of signals (digital or analog) originating from any well known communication equipment. For example, the input signal can represent digitized voice, digitized video signal or digital signals from a personal computer (PC) or computer system. Although not shown, it should be understood that the transmitter also comprises circuitry (e.g., Analog to Digital Converter) that converts analog signals to bits. Further, the transmitter comprises well known radio or other transmission circuitry configured to transmit digitally modulated signals which appear at the output of modulator 106.
Modulator 106 is designed to digitally modulate signals with the use of well known spectrally efficient modulation techniques such as Phase Shift Keying (PSK) or Differential Phase Shift Keying (DPSK). Generally, modulator 106 is an M-PSK or M-DPSK modulator where M represents the total number of different groupings of bits that can be transmitted by a digital modulator. For example for M=8, each grouping of bits contains N bits where N=log2 M. Thus, for M=8, N is equal to 3. The modulation process maps the incoming bits di (i=0, . . . , Ndxe2x88x921; where Nd is the number of bits in the sequence) into symbols (e.g., an M-PSK signal); one well known mapping technique is called Gray mapping which is shown in FIG. 2 for M=2, 4, 8. The symbols xi (i=0, . . . , Nkxe2x88x921; where Nk is the number of symbols in the sequence) are simply digital signals modulated in conformance with a particular modulation scheme (e.g., PSK). M-PSK and M-DPSK are examples of constant envelope modulation techniques because the maximum amplitude values of signals used to generate the symbols are relatively constant. When the maximum amplitude values of the signals used to generate the symbols are not constant, the modulation is referred herein as nonconstant envelope modulation. The output of modulator 106 (i.e., symbols xi) is then transmitted through channel 108 with the use of the aforementioned radio transmission circuitry. The incoming bits to modulator 106 are the output of interleaver 104 whose input signal is ci (i=0, . . . , Ncxe2x88x921; where Nc, is the number of bits in the sequence). The signal ci is a string or a grouping of bits, each of which is commonly referred to as a codeword, appearing at the output of convolutional encoder 102.
Convolutional encoder 102 is a well known bit processing device and/or function which, in essence, adds bits to the incoming bit stream bi (i=0, . . . , Nbxe2x88x921; where Nb is the number of bits in the sequence) to introduce redundancy in the incoming bits stream thus allowing for error correction at the receiver. The convolutionally encoded bits are represented by bit stream ci which is interleaved by interleaver 104. Interleaver 104 is also a well known bit processing device and/or function that alters the time order of the bits represented by ci thus introducing time diversity in a bit stream without adding bits to the bit stream. Although convolutional encoder 102, interleaver 104 and modulator 106 are described and depicted as separate devices, they can also be different parts of a signal processing and/or computer based system.
The receiver of the communication system model comprises a device hereinafter be referred to as Soft Output Detector (SOD) 110. The receiver further comprises Deinterleaver 112 and another device hereinafter referred to as Soft Input Decoder (SID) 114. SOD 110 is coupled to Deinterleaver 112 which is coupled to SID 114. It will be readily understood that the receiver typically comprises a plurality of receiving devices each of which is configured to receive a separate signal. For example the receiver shown in FIG. 1 comprises Na receiving devices (not shown) where Na is an integer equal to or greater than 1. In the case where the receiving device is an array of Na antennae, the communication system modeled in FIG. 1 may be, for example, a mobile communication system (i.e., a wireless communication system). In a mobile (wireless) communication system (and other communication systems) each antenna receives signals located in a certain frequency band. The received signal is downconverted (i.e., frequency content of the signal is changed to lower frequencies) and applied to a matched filter. The filtered signal is sampled at a rate greater than or equal to 1/T where T is a period of time that represents a signaling interval (i.e., the amount of time between transmission of two consecutive symbols). The samples (i.e., sampled received signals,yi) are fed to SOD 110. Further, well known receiver circuitry (e.g., amplifiers, filters), which are not shown, are also used to receive the plurality of different signals conveyed over channel 108. For the sake of simplicity and ease of illustration, the Na antennae and associated receiver circuitry are not shown. It will be readily understood that the receiver may be implemented with any well known receiving devices (other than antennae) that allow it to receive a plurality of separate signals. However, the receiving devices are hereinafter referred to as antennae simply for ease of discussion only. SOD 110 is a device that generates reliability information (xcexa9i) from the samples yi. 
The reliability information (or soft outputs) generated by SOD 110 represents a probability that the received signal is a particular group of bits from the set of bits defined by modulator 106 and examples of which are shown in FIG. 2, or the probability of each single bit within each transmitted symbol. It is important to note that the reliability information does not represent the actual transmitted signal but it provides an indication of the most likely signal that was transmitted. The output of SOD 110 (i.e., xcexa9i) is applied to Deinterleaver 112. Deinterleaver 112 performs the inverse operation of Interleaver 104 in that the signals xcexa9i are rearranged in their proper time order. The output of Deinterleaver 112 (xcexa9ixe2x80x2) is applied to Soft Input Decoder 114 (SID). SID 114 performs a decoding operation that serves to decode the output of Deinterleaver 112 into a stream of bits represented by bxe2x80x2i. Assuming the transmitter has a convolutional encoder, one example of a corresponding decoding operation is the Soft Input Viterbi Decoder which applies the well known Viterbi Decoding algorithm; G. D. Forney, xe2x80x9cThe Viterbi Algorithm,xe2x80x9d Proc. IEEE, March 1973, pp. 268-278.
Samples yi represent the transmitted symbols xi after they have propagated through channel 108. Channel 108 has well known characteristics (e.g., amplitude response, phase response, impulse response) that alter the transmitted symbols. As is well known in communication theory, the channel is a source of distortions, viz., multiplicative distortion, (e.g., phase jitter, amplitude degradation, frequency translation) that directly affect the transmitted symbols; such distortions are typically characterized mathematically using statistical and probability models. Furthermore, at the receiver noise components are added to the signal. Noise components are typically added by receiver circuitry and other circuitry. One example of noise is Additive White Gaussian Noise (AWGN). The channel characteristics and noise represent the effects of the channel on the transmitted sequence of symbols xi. The noise signals are represented by n. The multiplicative distortions from the channel are represented by h. The aggregate effect of the channel on the transmitted symbols (xi) is thus represented by characteristic h and noise n. The received samples (yi) are used to derive the reliability information. Channel State Information (CSI) is the total effect of the channel characteristic (h) (i.e., multiplicative distortion) on transmitted symbol. The CSI is equivalent to the impulse response (i.e., a function well known in electrical engineering that is used to fully describe a circuit) of the channel.
The goal of the receiver is to make a decision on the transmitted information bits bi from observing the sequence of sample yi. Such goal can be achieved by applying the well known MAP (Maximum A Posteriori) criteria. Since there exists a unique relation between the sequence of information bits bi (denoted as b) and the coded sequence of bits ci (denote as c), the MAP algorithm selects a codeword given a sequence of samples yi which have propagated through a channel having a certain characteristic represented by h; that is, the algorithm selects the codeword that maximizes the probability that the transmitted sequence was ci given that the input sequence to the receiver is yi. The probability being maximized is a conditional probability written as:
P(c|y, h)xe2x80x83xe2x80x83(1)
Equation (1) and all other equations appearing in this application follow the convention in which double underlined variables represent matrices and single underlined variables represent vectors. The sequence of signals received by the receiver after such signals have propagated through a channel with characteristic h and noise n is usually given as:
y=hx+nxe2x80x83xe2x80x83(2)
where n represents the noise signals existing in the channel and h represents multiplicative distortion from the channel. Thus, for a receiver having Na antennae coupled to channel 108 with each antenna being sampled at Nk (Nk is an integer equal to or greater than 1) distinct points in time at rate 1/T, equation (2) can be written in the following form:                                                                         [                                                                                                    y                                                  0                          ,                          0                                                                                                            …                                                                                      y                                                  0                          ,                                                      N                                                          k                              -                              1                                                                                                                                                                                                      …                                                              …                                                              …                                                                                                                          y                                                                              N                                                          a                              -                              1                                                                                ,                          0                                                                                                            …                                                                                      y                                                                              N                                                          a                              -                              1                                                                                ,                                                      N                                                          k                              -                              1                                                                                                                                                                          ]                            =                              xe2x80x83                            ⁢                              [                                                                                                    h                                                  0                          ,                          0                                                                                                            …                                                                                      h                                                  0                          ,                                                      N                                                          k                              -                              1                                                                                                                                                                                                      …                                                              …                                                              …                                                                                                                          h                                                                              N                                                          a                              -                              1                                                                                ,                          0                                                                                                            …                                                                                      h                                                                              N                                                          a                              -                              1                                                                                ,                                                      N                                                          k                              -                              1                                                                                                                                                                          ]                                                                                                        xe2x80x83                            ⁢                                                [                                                                                                              x                          0                                                                                            …                                                                    0                                                                                                            …                                                                    …                                                                    …                                                                                                            0                                                                    …                                                                                              x                                                      N                                                          k                              -                              1                                                                                                                                                            ]                                +                                  n                  =                                                                                        (        3        )            
The elements of the noise matrix n are equally distributed statistically independent complex Gaussian variables with zero mean and power E[|na,k|2]=2"sgr"a2. The real and imaginary components are independent zero mean Gaussian variables with standard deviation "sgr"a. It is well known that the first order statistics of a complex Gaussian random variable z with variance 2"sgr"a2 is given by a probability density function which is equal to:                               p          ⁡                      (            z            )                          =                              1                          2              ⁢                              πσ                a                2                                              ⁢                      e                                          -                                  1                                      2                    ⁢                                          σ                      a                      2                                                                                  ⁢                                                "LeftBracketingBar"                  z                  "RightBracketingBar"                                2                                                                        (3a)            
J. Proakis, Digital Communications, 3d edition, McGraw Hill, 1995. The characteristic, h (e.g., amplitude response, phase response) of channel 108 can be measured and then stored in matrix form as shown in equation (3). The transmitted symbols (xi) are represented by diagonal matrix x where each diagonal element is a particular symbol generated by modulator 106. The elements of the diagonal matrix x, matrix h and matrix n are complex numbers. The complex conjugate of h, x and n is denoted with the use of an asterisks, i.e., h*, x*, n*.
In essence, modulator 106 maps the sequence of input bits di into a sequence of symbols. The particular mapping (e.g., Gray mapping) used generates a finite number of distinct symbols. As shown by equation (3), the transmitted symbols xi are multiplied by h and then the noise is added. Equation (3) represents a communication system (e.g., mobile or wireless communication system) wherein a transmitted sequence of symbols propagates through a radio channel characterized by matrix h and captured by an antenna array with Na elements. In radio mobile communications systems (i.e., wireless communication systems), the distortion is manifested by rapid variations in amplitude and phase commonly referred to as fading.
The application of the MAP algorithm leads to a two-stage receiver. The first stage (SOD) generates reliability information on the coded bits di. After deinterleaving, the second stage (SID) applies a maximization rule to make a final decision on the most likely transmitted code word (c). In particular, assuming statistically independent coded bits, equation (1) can be written as:                     P        (                                            c              _                        ⁢                          "LeftBracketingBar"                                                y                  =                                ,                                  h                  =                                            )                                =                                    ∏                              l                =                0                                                              N                  c                                -                1                                      ⁢                          xe2x80x83                        ⁢                          P              (                                                c                  l                                ⁢                                  "LeftBracketingBar"                                                            y                      =                                        ,                                          h                      =                                                        )                                                                                        (        4        )            
where Nc represents the number of bits; Nc is equal number of symbols (i.e., samples)xc3x97number of bits/symbol or Nc=Nkxc3x97N. From the well known Bayes Rule in probability theory, (J. Proakis, Digital Communications, 3d edition, Mc Graw Hill, 1995) equation (4) is written as:                               P          (                                    c              _                        ⁢                          "LeftBracketingBar"                                                y                  =                                ,                                  h                  =                                                              )                =                              ∏                          l              =              0                                                      N                c                            -              1                                ⁢                      p            (                                          y                =                            ⁢                              "LeftBracketingBar"                                                      h                    =                                    ,                                      c                    l                                                  )                            ⁢                                                P                  ⁡                                      (                                          c                      l                                        )                                                                    p                  (                                                            y                      =                                        ⁢                                          "LeftBracketingBar"                                              h                        =                                            )                                                                                                                              (        5        )            
where p(y|h) and p(y|h, cl) are conditional probability density functions. Depending on the statistical nature of the transmitted symbols and the channel, a particular probability density function (typically Gaussian) is used for p(y|h, cl). Because, the goal is to maximize equation (5) over all possible codewords (c), p(y|h) is a constant since it does not depend on cl. The maximization operation can be done using the well known Viterbi algorithm or any other well known maximization algorithm, G. D. Forney, The Viterbi Algorithm, Proc. IEEE, March 1973. The maximization is performed by an outer stage of the receiver, i.e., SID 116. The result of the maximization of equation (5) is not altered when the logarithm (natural logarithm) of both sides of equation (5) is taken yielding:                     ln        ⁢                  xe2x80x83                ⁢                  P          (                                                    c                _                            ⁢                              "LeftBracketingBar"                                                      y                    =                                    ,                                      h                    =                                                  )                                      =                                          ∑                                  l                  =                  0                                                                      N                    c                                    -                  1                                            ⁢                              xe2x80x83                            ⁢                              {                                                      ln                    ⁢                                          xe2x80x83                                        ⁢                                          p                      (                                                                                                    y                            =                                                    ⁢                                                      "LeftBracketingBar"                                                                                          h                                =                                                            ,                                                              c                                l                                                                                      )                                                                          +                                                  ln                          ⁢                                                      xe2x80x83                                                    ⁢                                                      P                            (                                                          c                              l                                                        )                                                                                              }                                                        +                  C                                                                                        (5a)            
P(cl) is an a priori probability of coded bits cl. An a priori probability is either a given or known probability value or a probability value that is simply assumed or hypothesized. When all coded bits are equally likely, P(cl)xe2x88x92xc2xd. After deinterleaving, equation (5a) becomes:                     ln        ⁢                  xe2x80x83                ⁢                  P          (                                                    d                _                            ⁢                              "LeftBracketingBar"                                                      y                    =                                    ,                                      h                    =                                                  )                                      =                                          ∑                                  l                  =                  0                                                                      N                    c                                    -                  1                                            ⁢                              xe2x80x83                            ⁢                              {                                                      ln                    ⁢                                          xe2x80x83                                        ⁢                                          p                      (                                                                                                    y                            =                                                    ⁢                                                      "LeftBracketingBar"                                                                                          h                                =                                                            ,                                                              d                                l                                                                                      )                                                                          +                                                  ln                          ⁢                                                      xe2x80x83                                                    ⁢                                                      P                            (                                                          d                              l                                                        )                                                                                              }                                                        +                  C                                                                                        (5b)            
Since the interleaver maps a sequence of Nc input bits into one unique sequence of Nc output bits, the maximization of equations (5), (5a) over codewords c gives the same result as performing the maximization of equation (5b) over interleaved codewords d.
The terms of the sum in equation (5b) are log likelihood functions calculated by SOD 110. Thus, the task of SOD 110 is to produce the following log likelihood function:
xcexa9(dl)=ln p(y|h, dl)+ln P(dl)xe2x80x83xe2x80x83(6)
Equation (6) is the output of SOD 110 that is then applied to Deinterleaver 112. Equation (6) is therefore produced from the samples y. Thus, the log likelihood function of the ith bit in the mth time interval is expressed as:
xcexa9m,i(b)=ln p(y|h, dm,i=b)+ln P(dm,i=b) where b=0,1xe2x80x83xe2x80x83(7)
Equation (7) expresses the logarithm of the probability that the ith bit belonging to the symbol received at the mth time interval is a certain value. The log likelihood function xcexa9 of equation (7) can be interpreted mathematically as a transform from the space of observations y to the space of the logarithm of probabilities P. It should be noted that if xcexa9m,i(1) is greater than xcexa9m,i(0), then the transmitted bit dm,i is more likely to be 1 than 0. Because there is a direct mapping between the variables x and d, the log likelihood function of equation (7) can be computed using the probability density function p(y|h,x); this probability density function is expressed as:                     p        (                                            y              =                        ⁢                          "LeftBracketingBar"                                                h                  =                                ,                                  x                  _                                            )                                =                                    ∏                              a                =                0                                                              N                  a                                -                1                                      ⁢                          p              (                                                                    y                    _                                                                              xe2x80x83                                        ⁢                    a                                                  ⁢                                  "LeftBracketingBar"                                                                                    h                        _                                                                                              xe2x80x83                                                ⁢                        a                                                              ,                                          x                      _                                                        )                                                                                        (        8        )            
Equation (8) expresses the concept of independent channels (each antenna serves a particular channel) by each of the Na antennae; that is, the channels associated with each antennae are independent from any other channels. The antennae are statistically independent from each other, thus the factorization in equation (8) holds where each factor (ya) represents a sequence of samples received by an antenna a. Given the AWGN assumption, equation (8) can also be factored over time samples where each factor (yk) represents a sequence of samples received at time k by all antennae:                     p        (                                            y              =                        ⁢                          "LeftBracketingBar"                                                h                  =                                ,                                  x                  _                                            )                                =                                    ∏                              k                =                0                                                              N                  k                                -                1                                      ⁢                          p              (                                                                    y                    _                                                                              xe2x80x83                                        ⁢                    k                                                  ⁢                                  "LeftBracketingBar"                                                                                    h                        _                                                                                              xe2x80x83                                                ⁢                        k                                                              ,                                          x                      k                                                        )                                                                                        (        9        )            
Combining equations (8) and (9) the joint probability density function for all Nk samples of each of the Na antenna is obtained:                               p          (                                    y              =                        ⁢                          "LeftBracketingBar"                                                h                  =                                ,                                  x                  _                                                              )                =                              ∏                          a              =              0                                                      N                a                            -              1                                ⁢                                    ∏                              k                =                0                                                              N                  k                                -                1                                      ⁢                          p              (                                                                    y                                          a                      ,                      k                                                        ⁢                                      "LeftBracketingBar"                                                                  h                                                  a                          ,                          k                                                                    ,                                              x                        k                                                                                            )                                                                        (        10        )            
Combining equation (10) with equation (7), the log likelihood function can be expressed as follows:                                           Ω                          m              ,              i                                ⁡                      (            b            )                          =                  ln          ⁢                                    ∑                                                x                  _                                ∈                                                      X                    _                                    ⁡                                      (                                          d                                              m                        ,                        i                                                              )                                                                        ⁢                          xe2x80x83                        ⁢                          p              ⁢                              "AutoLeftMatch"                                                                            (                      "AutoRightMatch"                                        ⁢                                          y                      =                                        ⁢                                          "LeftBracketingBar"                                                                        h                          =                                                ,                                                                              x                            _                                                    ⁢                                                      "AutoLeftMatch"                            )                                                                                              "AutoRightMatch"                                                        =                                      ln                    ⁢                                                                  ∑                                                                              x                            _                                                    ∈                                                                                    X                              _                                                        ⁡                                                          (                                                              d                                                                  m                                  ,                                  i                                                                                            )                                                                                                                          ⁢                                              (                                                                              ∏                                                          a                              =                              0                                                                                                                      N                                a                                                            -                              1                                                                                ⁢                                                      xe2x80x83                                                    ⁢                                                                                    ∏                                                              k                                =                                0                                                                                                                              N                                  k                                                                -                                1                                                                                      ⁢                                                          xe2x80x83                                                        ⁢                                                          p                              (                                                                                                                                                                          y                                                                              a                                        ,                                        k                                                                                                              ⁢                                                                          "LeftBracketingBar"                                                                                                                        h                                                                                      a                                            ,                                            k                                                                                                                          ,                                                                                  x                                          k                                                                                                                                                                                      )                                                                ⁢                                                                  P                                  ⁡                                                                      (                                                                          x                                      _                                                                        )                                                                                                                              )                                                                                                                                                                                                                                  (        11        )            
X(dm,i) is the set of all possible transmitted sequences of symbols (x) that have bit dm,i=b. Therefore, as shown in equation (11), in order to compute the reliability information all possible transmitted sequences, their probabilities and the density functions (equations (8) and (9)) have to be determined. Thus, the generation of the reliability information is tedious and complex requiring many calculations. What is therefore needed is an efficient method of calculating the reliability information generated by SOD 110.
The present invention provides an efficient method for calculating reliability information (soft output) using a Soft Output Detector. The reliability information is calculated from received samples and a priori information. The received samples are symbols generated by a modulator which symbols have propagated through a communication channel. The received samples are applied to a Soft Output Detector that is part of a receiver comprising Na receiving devices where Na is an integer equal to or greater than 1. The method of the present invention has a first step of receiving a first sample and a second sample. An algebraic expression is evaluated from the first sample and/or second sample and from a priori information associated with the information contained in the transmitted symbols. The reliability information is then derived from the algebraic expression.